#!/usr/bin/env python

import util
import numpy as np
import math

class Element(object):

    def __init__(self, element):
        self.element = element
        self.parent = None
    def assign(self, parent):
        self.parent = parent

class Bucket(object):
    def __init__(self,prev, next) :
        self.value = 1
        self.elements = set([])
        self.next = self if next == None else next
        self.prev = self if prev == None else prev
    def remove(self, element):
        del self.elements[element]
        if len(self.elements) == 0 :
            if self.prev == self or self.next == self :
                return (None, None, True)
            else :
                return (self.prev, self.next, True)
        else :
            (self, self.next, False)

    def add(self, element):
        self.elements.add(element)
        element.assign(self)
    def update(self, prev, next):
        if self.next == self or self.next == p_old:
            self.next = p_new
            self.prev = p_new
        ######

    def setPrev(self, prev):
        self.prev = prev
    def setNext(self, next):
        self.next = next
    def min_replace(self, element):
        element.assign(self)
        self.elements = set([element])
        self.value+=1

class StreamSummary(object):
    def __init__(self, k):
        self.min = None
        self.elements = {}
        self.k = k

    def insert(self, key):
        if key in self.elements :
            element = self.elements[key]
            if (element.parent.next.value == element.parent.value +1) :
                element.parent.next.add(element)
                (prev,next, isEmpty) = element.parent.remove(element)
                if isEmpty :
                    prev.updatePrev(next)
                    next.setPrev(prev)
                    prev.setNext(next)
                    del element.parent

        elif len(self.elements) < self.k :
            element = Element(key)
            if self.min == None :
                self.min = Bucket(None, None)
                self.min.add(element)

            elif self.min.value == 1 :
                self.min.add(element)

            else :
                prev = self.min.prev
                next = self.min
                bucket = Bucket(prev, next)
                bucket.add(element)
                self.min.setPrev(bucket)
                prev.setNext(bucket)
                            # increase counter

            self.elements[key] = element
        else :
            element = Element(key)
            if self.min.value == 1 :
                self.min.add(element)
            else :
                self.min.min_replace(element)
            self.elements[key] = element

            # insert new element

def main():
    def callback(*args, **kwargs):
        print (args, kwargs)

    size_k = 10
    tests = 10
    base = 1000000
    stat = [0 for x in range(1,tests)]
    for i in range(tests) :
        stream = np.random.zipf(2.8, base * math.pow(2,i))
        with util.Timer() as t :
            ss = StreamSummary(size_k)
            for el in stream :
                ss.insert(el)
        print('Summary took %.03f sec.' % t.interval)
        stat.append((str(base * math.pow(2,i)), t.interval))

    print stat